The present invention relates to storing data in computer memories such as flash memories and, more particularly, to a method of storing data in a computer memory in a manner that enables the cells that store the data to include a small number of “bad” cells.
Flash memory devices have been known for many years. Typically, each memory cell within a flash memory stores one bit of information. The traditional way to store a bit in a flash memory cell has been by supporting two states of the cell. One state represents a logical “0” and the other state represents a logical “1”. In a flash memory cell, the two states are implemented by having a floating gate above the cell's channel (the area connecting the source and drain elements of the cell's transistor), and having two valid states for the amount of charge stored within the floating gate. Typically, one state is with zero charge in the floating gate and is the unwritten state of the cell after being erased (commonly defined to represent the “1” state) and the other state is with some amount of negative charge in the floating gate (commonly defined to represent the “0” state). Negative charge is imposed on the floating gate by applying voltage pulses to the cell to inject electrons from the cell's silicon substrate through the cell's oxide layer into the floating gate until the threshold voltage is high enough to represent the “0” state. Having negative charge in the gate causes the threshold voltage of the cell's transistor (i.e. the voltage that has to be applied to the transistor's control gate in order to cause the transistor to conduct) to increase. It is possible to read the stored bit by checking the threshold voltage of the cell. If the threshold voltage is in the higher state then the bit value is “0” and if the threshold voltage is in the lower state then the bit value is “1”. Actually there is no need to accurately read the cell's threshold voltage. All that is needed is to correctly identify in which of the two states the cell is currently located. For this purpose it is sufficient to compare the threshold voltage of the cell to a reference voltage that is between the two states, and to determine if the cell's threshold voltage is below or above the reference value.
FIG. 1A (prior art) shows graphically how this works. Specifically, FIG. 1A shows a distribution of the threshold voltages of a large population of cells. Because the cells in a flash device are not exactly identical in their characteristics and behavior (due to, for example, small variations in impurity concentrations or defects in the silicon structure), applying the same writing operation to all the cells does not cause all the cells to have exactly the same threshold voltage. Instead, the threshold voltage is distributed as shown in FIG. 1A. Cells storing a value of “1” typically have a negative threshold voltage, such that most of the cells have a threshold voltage close to the central voltage value of the left peak (labeled 1) of FIG. 1A, with fewer cells having threshold voltages lower or higher than the central voltage of the left peak. Similarly, cells storing a value of “0” typically have a positive threshold voltage, such that most of the cells have a threshold voltage close to the central voltage of the right peak (labeled 0) of FIG. 1A, with fewer cells having threshold voltages lower or higher than the central voltage of the right peak.
For historical reasons, writing data to a flash memory cell also is called “programming” the flash cell. The terms “writing” and “programming” are used interchangeably herein.
In recent years, a new kind of flash device has appeared on the market, using “Multi Level Cells” (MLC). The term “Multi-Level Cell” is misleading because flash memory with a single bit per cell uses multiple i.e. two levels, as described above. Therefore, the term “Single Bit Cell” (SBC) is used hereinafter to refer to a memory cell of two levels and the term “Multi-Bit Cell” (MBC) is used hereinafter to refer to a memory cell of more than two levels, i.e. more than one bit per cell. The technology presented herein is described with reference to an MBC flash memory with two bits per cell. It should however be understood that the technology presented herein is equally applicable to flash memory devices that support more than two bits per cell.
A single MBC cell storing two bits of information is in one of four different states. As the cell's “state” is represented by the cell's threshold voltage, an MBC cell supports four different valid ranges for the cell's threshold voltage. FIG. 1B (prior art) shows the threshold voltage distribution for a typical MBC cell of two bits per cell. As expected, FIG. 1B has four peaks, each peak corresponding to one state. As for the SBC, each state is actually a voltage range and not a single voltage. When reading the cell's contents, the cell's threshold voltage must be correctly identified in a definite voltage range.
The programming of a MBC flash cell is not foolproof. Consider, for example, how the ten binary numbers 11, 01, 11, 01, 11, 00, 10, 00, 10, 00 might be stored in ten MBC cells. The mapping of threshold voltages to bit patterns is as illustrated in FIG. 1B:
State NumberThreshold voltage bandBit pattern0<0 V111Between 0 V and 1 V102Between 1 V and 2 V013>2 V00The most significant bits (1010101010) are stored by programming the second, fourth, sixth, eighth and tenth cells into the 1V-2V threshold voltage band. The least significant bits (1111100000) then are stored by programming the sixth, eight and tenth cells into the >2V threshold voltage band and by programming the seventh and ninth cells into the 0V-1V threshold voltage band. Physical effects, such as programming variations, program disturb and cross coupling, during the programming of the most significant bits and between the programming of the most significant bits and the programming of the least significant bits, might cause e.g. the second cell to be placed inadvertently in the >2V band before the least significant bits are programmed, thereby making it impossible for the second cell to store the desired “01” bit pattern without erasing the cell and starting over, because programming operations only increase the threshold voltage of a cell. But flash memory cells are erased a full block of cells at a time and it is not practical to erase a full block of cells merely for correcting an error in a small number of cells.
This kind of error, in which a flash memory cell is placed in an intermediate state, during programming, from which the desired final state of the cell cannot be reached by further programming without erasing the cell, is referred to herein as “overprogramming” the cell. A cell that has experienced such over-programming is referred to herein as an “overprogrammed” cell.
Overprogramming is not the only reason that the programming of an MBC flash cell is not foolproof. After the wear and tear of many programming and erasure cycles, a flash cell may be stuck permanently in one of its threshold voltage states. For example, the condition of a cell in its erase state (storing “11” according to the table above) may be such that no amount of programming can budge the cell from the erase state, or the condition of a cell in its most programmed state (storing “00” according to the table above) may be such that no amount of erasing can budge the cell from the most programmed state.
Conventionally, problems of this kind are handled by encoding the data to be stored as codewords that are stored instead of the data, and hoping that the encoding is strong enough to overcome both these programming errors and subsequent errors such as drift of the threshold voltages over time.
Tutorial on GF(2t+1)
One of the methods described below is based on the Galois field GF(2t+1).
GF(2t+1) is a set of 2t+1 elements with well defined operations of summation, multiplication and division. The elements in the field can be represented as binary vectors of length t+1 Alternatively, the field elements can be represented as binary polynomials of degree at most t with well-defined operations of summation, multiplication and division.
Each element of GF(2t+1) is associated with a vector of t+1 coordinates and with a polynomial of degree at most t over GF(2) in the following manner:a=(a0,a1,L,at)pa(x)=a0+a1x+L+atxt The coefficients of the polynomial pa(x) are elements in GF(2) (i.e., either 0 or 1) and summation of pa(x) and pb(x) is defined as:
                    p        a            ⁡              (        x        )              +                  p        b            ⁡              (        x        )              =                              ∑                      j            =            0                    t                ⁢                              (                                          a                j                            ⊕                              b                j                                      )                    ·                      x            j                              |                        a          b                ⊕                  b          j                      =          a      +              b        ⁢                                  ⁢        modulo        ⁢                                                  ⁢                                                ⁢        2            
Multiplication of two elements, a,b is done by multiplication of the associated polynomials pa(x), pb(x) and taking the result modulo a predefined irreducible polynomial g(x) of degree t+1 over GF(2). The multiplication result a·b can be represented as a binary vector of length t+1 over GF(2), where each coordinate is a binary linear combination of elements (coefficients) of a and elements (coefficients) of b.
To complete the picture, the inverse and the division operation are defined. Each non-zero element a of GF(2t+1) has a unique inverse element denoted a−1, such that a·a−1=a−1·a=1. Division by a is equivalent to multiplication by a−1.